package leetcode.m1.d1;

//abcdefg
//        ac

public class Solution {
    public static void main(String[] args) {
        int contains = contains("aab", "ababab");
        System.out.println(contains);
    }

//    abaabad

    public static int contains(String needle, String pattern) {
        char[] chars = needle.toCharArray();
        char[] chars1 = pattern.toCharArray();
        //next 数组
        int[] next = new int[pattern.length()];
        int j = 0;
        next[0] = j;
        for (int i = 1; i < pattern.length(); i++) {

            while (j >= 1 && chars1[i] != chars1[j]) {
                j = next[j - 1];
            }

            if (chars1[j] == chars1[i]) {
                j++;
            }
            next[i] = j;
        }

        if (chars1.length > chars.length) {
            return -1;
        }
        int p = 0, m = 0;
        while (p < chars.length) {
            while (chars[p] == chars1[m]) {
                p++;
                m++;
                if (m == chars1.length) {
                    return p - chars1.length;
                }
                if (p == chars.length) {
                    return -1;
                }
            }
            if (m > 0) {
                m = 0;
            } else {
                p++;
            }
        }
        return -1;
    }
}
